package 中等.数学;

/**
 * 给定一个长度为 n 的整数数组 nums 。
 * 假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数  F 为：
 * F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
 * 返回 F(0), F(1), ..., F(n-1)中的最大值 。
 * 生成的测试用例让答案符合 32 位 整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-function
 */
public class 旋转函数_396 {

    public static void main(String[] args) {

        int[] nums = {4, 3, 2, 6};
        System.out.println(maxRotateFunction(nums));

    }

    /**
     * 不用考虑溢出int类型
     * 找规律：
     * [4,3,2,6]
     * F(0) = 0*4+1*3+2*2+3*6
     * 顺时针旋转1个位置，末尾元素放置到首位，其余元素向后退一位，后的数组[6,4,3,2]
     * F(1) = 0*6+1*4+2*3+3*2
     * 发现除了最后一个元素 - (n-1)*nums[curIdx] ，其余原都增加了一倍
     * 预先算出数组总和 numSum ，由于最后一个元素不在增加范围内，需要+numSum之后，-nums[curIdx]
     * F(2)= F(1)+numSum-(n-1)*nums[i]-nums[i] = F(1)+numSum-n*nums[i]
     * 先遍历算出F(0)后面的...F(n-1)通过动态规划计算
     *
     * @param nums
     * @return
     */
    public static int maxRotateFunction(int[] nums) {
        int ans;
        int numSum = 0, preFSum = 0;
        for (int i = 0; i < nums.length; i++) {
            numSum += nums[i];
            preFSum += i * nums[i];
        }
        ans = preFSum;
        for (int i = nums.length - 1; i > 0; i--) {
            int curFSum = preFSum + numSum - nums.length * nums[i];
            ans = Math.max(ans, curFSum);
            preFSum = curFSum;
        }
        return ans;
    }

}
